package cn.suchan.jianzhi.q4_tree;

/**
 * 知识点：重建二叉树
 * 题目描述
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 * （
 * 前序遍历：根节点->左节点->右节点
 * 中序遍历：左节点->根节点->右节点
 * 后序遍历：左节点->右节点->根节点
 * ）
 *
 * @author suchan
 * @date 2019/05/23
 */
public class Solution {

    /**
     * 第一种方法
     *
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConBinTre(int[] pre, int[] in) {
        if (pre.length == 0) {
            return null;
        }
        //pre[0]是根
        int rootnode = pre[0];
        TreeNode root = new TreeNode(rootnode);

        // 如果长度为1，则表明这棵树只有一个根节点
        // 由于一棵树的节点数是相同的，所以len取pre或in都可以
        int len = pre.length;
        if (len == 1) {
            root.left = null;
            root.right = null;
            return root;
        }
        //找到中序遍历中根节点的下标
        int inRoot;
        for (inRoot = 0; inRoot < len; inRoot++) {
            if (rootnode == in[inRoot]) {
                break;
            }
        }
        // inRoot大于0，表示存在左子树
        if (inRoot > 0) {
            int[] pre_left = new int[inRoot];
            int[] in_left = new int[inRoot];
            for (int j = 0; j < inRoot; j++) {
                pre_left[j] = pre[j + 1];
            }
            for (int j = 0; j < inRoot; j++) {
                in_left[j] = in[j];
            }
            root.left = reConBinTre(pre_left, in_left);
        } else {
            root.left = null;
        }
        //创建右子树
        if (len - inRoot - 1 > 0) {
            int[] pre_right = new int[len - inRoot - 1];
            int[] in_right = new int[len - inRoot - 1];
            // j=inRoot+1,因为inRoot为中序根节点位置，也为前序遍历左子树的最后一个节点的位置
            for (int j = inRoot + 1; j < len; j++) {
                pre_right[j - inRoot - 1] = pre[j];
                in_right[j - inRoot - 1] = in[j];
            }
            root.right = reConBinTre(pre_right, in_right);
        } else {
            root.right = null;
        }
        return root;
    }

    /**
     * 第二种方法
     *
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return root;
    }

    /**
     * @param pre      前序遍历数组
     * @param startPre 前序遍历数组的开始下标
     * @param endPre   前序遍历数组的结束下标
     * @param in       中序遍历
     * @param startIn  中序遍历数组的开始下标
     * @param endIn    中序遍历数组的结束下标
     * @return
     */
    private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {

        if (startPre > endPre || startIn > endIn) {
            return null;
        }

        // 前序遍历的第一个元素即为根节点
        TreeNode root = new TreeNode(pre[startPre]);

        for (int i = startIn; i <= endIn; i++) {
            // 在中序遍历中查找根节点所在位置，其左侧为左子树，其右侧为右子树
            if (in[i] == pre[startPre]) {
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int pre[] = {1, 2, 4, 5, 7, 8, 3, 6};
        int in[] = {4, 2, 7, 5, 8, 1, 3, 6};

        /*TreeNode treeNode = solution.reConstructBinaryTree(pre, in);*/
        TreeNode treeNode = solution.reConBinTre(pre, in);

        System.out.println("tree==>" + treeNode);
    }
}
